package cn.xdf.learn.leetcode.动态规划;

import java.util.ArrayList;
import java.util.List;

public class 杨辉三角 {

    public static void main(String[] args) {
        杨辉三角 s = new 杨辉三角();
//        List<List<Integer>> generate = s.generate(5);
//        System.out.println(generate);
        s.getRow(3);
    }


    /**
     * 给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。
     * @param rowIndex
     * @return
     */
    public List<Integer> getRow(int rowIndex) {
        List<List<Integer>> generate = generate(rowIndex+1);
        return generate.get(rowIndex);
    }


    /**
     * 给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
     *
     * 在「杨辉三角」中，每个数是它左上方和右上方的数的和。
     * @param numRows
     * @return
     */
    public List<List<Integer>> generate(int numRows) {


        int [][] dp = new int[numRows][numRows];

        dp[0][0] = 1;
        if (numRows == 1){
            return arraysToList(dp);
        }

        for (int i = 1; i < numRows; i++) {

            for (int j = 0; j < numRows; j++) {
                if (j == 0 || j == i){
                    dp[i][j] = 1;
                    continue;
                }
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
            }

        }


        return arraysToList(dp);

    }




    private List<List<Integer>> arraysToList(int [][] dp){
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < dp.length; i++) {
            List<Integer> list = new ArrayList<>();
            for (int j = 0; j < dp[i].length; j++) {
                if (dp[i][j] == 0){
                    continue;
                }
                list.add(dp[i][j]);
            }
            result.add(list);
        }
        return result;
    }
}
